import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-03-10
 * Time: 23:06
 */
class RandomizedSet {


    /**
     * LeetCode 380  O(1)时间插入  删除  和获取随机元素
     */

    List<Integer> nums;
    Map<Integer,Integer> indices;
    Random random;

    public RandomizedSet() {
        nums = new ArrayList<Integer>();
        indices = new HashMap<Integer,Integer>();
        random = new Random();

    }

    public boolean insert(int val) {
        // 如果存在就插入失败
        if(indices.containsKey(val)){
            return false;
        }
        int index = nums.size();
        nums.add(val);
        // 模拟数组
        indices.put(val,index);
        return true;
    }

    public boolean remove(int val) {
        if(!indices.containsKey(val)){
            return false;
        }
        int index = indices.get(val);
        // 记录当前数组位置
        int last = nums.get(nums.size()-1);
        nums.set(index,last);
        indices.put(last,index);
        nums.remove(nums.size()-1);
        indices.remove(val);
        return true;
    }

    public int getRandom() {
        int randomIndex = random.nextInt(nums.size());
        return nums.get(randomIndex);
    }
}
